package com.smh;

import java.util.PriorityQueue;

/**
 * @author shiminghui
 * @date 2025/2/20 15:37
 * @description: TODO
 */
public class _030_堆练习 {

    class MedianFinder {

        private PriorityQueue<Integer> minQueue;
        private PriorityQueue<Integer> maxQueue;
        private int count;

        public MedianFinder() {
            minQueue = new PriorityQueue<>(
                    (o1, o2) -> {
                        return Integer.compare(o1, o2);
                    }
            );
            maxQueue = new PriorityQueue<>(
                    (o1, o2) -> {
                        return Integer.compare(o2, o1);
                    }
            );
        }

        public void addNum(int num) {
            if (count % 2 == 0) { // 插入大根堆，（先插入小根堆，再从小根堆取出最小的，加入大根堆）
                minQueue.offer(num);
                Integer poll = minQueue.poll();
                maxQueue.offer(poll);
            } else {
                maxQueue.offer(num);
                Integer poll = maxQueue.poll();
                minQueue.offer(poll);
            }
            count++;
        }

        public double findMedian() {
            if (count % 2 == 0 && count != 0) {
                Integer right = minQueue.peek();
                Integer left = maxQueue.peek();
                return (right + left) / 2.0;
            } else if (count % 2 != 0) {
                return maxQueue.peek();
            } else {
                return -1;
            }
        }
    }
}
